#include <dbg.h>

#include <cassert>

using namespace std;

class Solution {
public:
    int equalSubstring(string s, string t, int maxCost) {
        int res = 0;
        int left = 0;
        int cost = 0;  // 记录窗口内的花费
        for (int right = 0; right < s.size(); ++right) {
            cost += abs(s[right] - t[right]);  // 记录窗口内的花费
            while (cost > maxCost) {  // 窗口内的花费大于maxCost，就需要缩小窗口
                cost -= abs(s[left] - t[left]);
                ++left;
            }
            res = max(res, right - left + 1);
        }
        return res;
    }
};

int main() {
    Solution s;
    string s1 = "abcd", t1 = "bcdf";
    int maxCost1 = 3;
    assert(s.equalSubstring(s1, t1, maxCost1) == 3);
    string s2 = "abcd", t2 = "cdef";
    int maxCost2 = 3;
    assert(s.equalSubstring(s2, t2, maxCost2) == 1);
    string s3 = "abcd", t3 = "acde";
    int maxCost3 = 0;
    assert(s.equalSubstring(s3, t3, maxCost3) == 1);
    return 0;
}